(define parse
  \D is the distinguished symbol of the grammar\
  D Sentence -> (let Parse (D [Sentence []])
                   (if (parsed? Parse) (output_parse Parse) ungrammatical)))

(define parsed?
  [[] Output] -> true
  _ -> false)

(define output_parse
  [_ Output] -> Output)

(define generate_parser
  Grammar -> (map compile_rules (group_rules (parenthesise_rules Grammar))))

(define parenthesise_rules
  [S --> | Rest] -> (parenthesise_rules1 [S -->] Rest))

(define parenthesise_rules1
  Rule [] -> [Rule]
  Rule [S --> | Rest] -> [Rule | (parenthesise_rules1 [S -->] Rest)]
  Rule [X | Y] -> (parenthesise_rules1 (append Rule [X]) Y))

(define group_rules
  Rules -> (group_rules1 Rules []))

(define group_rules1
  [] Groups -> Groups
  [Rule | Rules] Groups -> (group_rules1 Rules (place_in_group Rule Groups)))

(define place_in_group
  Rule [] -> [[Rule]]
  Rule [Group | Groups] -> [[Rule | Group] | Groups]
        where (belongs-in? Rule Group)
  Rule [Group | Groups] -> [Group | (place_in_group Rule Groups)])

(define belongs-in?
  [S | _] [[S | _] | _] -> true
  _ _ -> false)

(define compile_rules
  Rules -> (if (lex? Rules)
               (generate_code_for_lex Rules)
               (generate_code_for_nonlex Rules)))

(define lex?
  [[S --> Terminal] | _] -> (string? Terminal)
  _ -> false)

(define generate_code_for_nonlex
  Rules -> (eval (append [define (get_characteristic_non_terminal Rules) 
                                    | (mapapp gcfn_help Rules)] 
                         [X -> #\Escape])))

(define mapapp
  _ [] -> []
  F [X | Y] -> (append (F X) (mapapp F Y)))

(define get_characteristic_non_terminal
  [[CNT | _] | _] -> CNT)

(define gcfn_help
   Rule -> [Parameter
            <-
            (apply_expansion Rule
                             [list [head Parameter]
                                   [cons [list | Rule]
                                         [head [tail Parameter]]]])])
 
(define apply_expansion
   [CNT --> | Expansion] Parameter -> (ae_help Expansion Parameter))

(define ae_help
   [] Code -> Code
   [NT | Expansion] Code -> (ae_help Expansion [NT Code]))

(define generate_code_for_lex
  Rules -> (eval (append [define (get_characteristic_non_terminal Rules)
                                   #\Escape -> #\Escape
                                   | (mapapp gcfl_help Rules)]
                         [X -> #\Escape])))

(define gcfl_help
  [CNT --> Terminal] -> [[list [cons Terminal P] Parse]
                          -> [list P [cons [list CNT --> Terminal] Parse]]])

